\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{作业一: \textbf{双链表}的设计和实现}


\author{胡宇梦 \\ 信息与计算科学　3210103435}


\begin{document}

\maketitle




\section{项目设计思路}
双链表，是链表的一种，它的每个数据节点中都有两个指针，
分别指向直接后向和直接前向。所以，从双向链表中的任意一个节点开始，都可以很方便地访问它的前向节点和后向节点。
在考虑设计一个双链表的时候，我们需要完成以下内容：
\begin{enumerate}
\item 节点的定义

对于双向链表,每一个节点都与其前向、后向的连接，那么这个链接我们通过指向节点的指针来完成。
指向节点的指针在解引用之后就是一个节点对象。
\item 迭代器的定义

我们使用迭代器来对双向链表完成统一的遍历访问功能，最典型的迭代器就是指针。
\item 方法的实现

在末尾插入，删除元素；在链表首部插入、删除元素；
可以像访问数组元素一样使用运算符对链表元素进行访问。

\end{enumerate}




\section{实现与测试说明}
\begin{enumerate}
  \item \textbf{节点的定义使用}


这一个部分，我们定义了Node 的节构体作为一个节点的存储单元。
其中有三个属性： data 存储值，prev指向此节点的前向指针，next 指向此节点的后向指针。
\begin{verbatim}
  struct Node
 {
		/// @brief 节点数据.
		DT data;

		/// @brief 节点前向指针.
		Node *prev;

		/// @brief 节点后向指针.
		Node *next;

		/**
		 * @brief 节点的构造函数.
		 *
		 * @param d 初始化节点数据.
		 * @param p 初始化前向指针.
		 * @param n 初始化后向指针.
		 */
		Node(const DT &d = DT{}, Node *p = nullptr, Node *n = nullptr)
     : data{d}, prev{p}, next{n} {}

		/**
		 * @brief 节点的移动构造函数.
		 *
		 * @param d 初始化节点数据.
		 * @param p 初始化前向指针.
		 * @param n 初始化后向指针.
		 */
		Node(DT &&d, Node *p = nullptr, Node *n = nullptr) 
    : data{std::move(d)}, prev{p}, next{n} {}
	};
\end{verbatim}

\item\textbf{迭代器的定义使用}


迭代器不是指针，是类模板，表现的像指针，只是模拟了指针的一些功能，
通过重载了指针的一些操作符等封装了指针，是一个可以遍历STL容器内全部或者部分元素的对象。


本项目定义了两个迭代器类，const\_iterator和iterator，其中const\_iterator类是iterator类的父类，
两种迭代器都可以访问元素，区别在于const\_iterator不可以更改元素，iterator类可以更改元素。


\item\textbf{方法的实现与测试}

\subsection*{3.1 创建双链表对象list}  
代码如下： 
\begin{verbatim}
DoubleLinkedList<int> list;
\end{verbatim}

\subsection*{3.2 头部插入节点}  
代码如下： 
\begin{verbatim}
list.push_back(1);    //头部插入节点
list.push_back(2);
list.push_back(3);
list.push_back(4);
list.push_back(5);
\end{verbatim}

\subsection*{3.3 遍历输出}  
代码如下： 
\begin{verbatim}
void printList(DoubleLinkedList<int>&\_list)
{
  for(DoubleLinkedList<int>::iterator i = \_list.begin();i != \_list.end();i++ )
        cout << *i <<endl;
}
\end{verbatim}
测试代码：
\begin{verbatim}
  printList(list);
\end{verbatim}
测试结果：
\begin{verbatim}
  1
  2
  3
  4
  5
\end{verbatim}

\subsection*{3.4 读取链表长度 size()}  
代码如下： 
\begin{verbatim}
int size() const
	{
		return theSize;
	}
\end{verbatim}
测试代码：
\begin{verbatim}
cout<<list.size()<<endl;
\end{verbatim}
测试结果：
\begin{verbatim}
  5
\end{verbatim}

\subsection*{3.5 判断链表是否为空 empty()}
代码如下： 
\begin{verbatim}
bool empty() const
{
  return size() == 0;
}
\end{verbatim}
测试代码：
\begin{verbatim}
cout<<list.empty()<<endl;
\end{verbatim}
测试结果：
\begin{verbatim}
  0
\end{verbatim}

\subsection*{3.6 插入数据 insert()}
代码如下： 
\begin{verbatim}
iterator insert(iterator itr, const DT &x)
	{
		cout << "调用左值插入函数" << endl;
    Node *p = itr.current;

		theSize++;

		return {p->prev = p->prev->next = new Node{x, p->prev, p}};
	}
iterator insert(iterator itr, DT &&x)
	{
		cout << "调用右值插入函数" << endl;
    Node *p = itr.current;
		theSize++;
		return {p->prev = p->prev->next= new Node{std::move(x), p->prev, p}};
	}
\end{verbatim}
测试代码：
\begin{verbatim}
int a = 10;
insert ( \_list.begin() , a );
insert ( \_list.end() , 9 );
printList(list);
\end{verbatim}
测试结果：
\begin{verbatim}
  调用左值插入函数
  调用右值插入函数
  10
  1
  2
  3
  4
  5
  9
\end{verbatim}

\subsection*{3.5 查找数据 外部自定义函数find()}
代码如下： 
\begin{verbatim}
DoubleLinkedList<int>::iterator find(DoubleLinkedList<int>& _list, const int& _val)
  {
    int f = 0;
    for (DoubleLinkedList<int>::iterator i = _list.begin(); i != _list.end(); i++)
    {
      if (*i == _val)
      {
        f = 1;
        cout << "查找成功,已返回该节点迭代器" << endl;
        return i;
      }
    }
    if (f == 0)
    {
      cout << "查找失败，已返回该链表末端节点迭代器" << endl;
      return _list.end();
    }
  }
\end{verbatim}
测试代码：
\begin{verbatim}
DoubleLinkedList<int> L;
L.push_back(1);
L.push_back(2);
L.push_back(3);
L.push_back(4);
printList(L);
DoubleLinkedList<int>::iterator itr;
itr = find(L, 3);
list.erase(itr);
printList(L);
itr = find(L, 3);
\end{verbatim}
测试结果：
\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.5]{1.jpg}
  \caption{测试结果}
\end{figure}  

\end{enumerate}

\section{对模板的修改}
在书中双链表实现模板的基础上，我们完善了对迭代器自减运算符的重载，从而实现自减的函数运用。

\section{总结}
list是数据结构中常被使用的容器，

其优点是：采用动态存储分配，不会造成内存浪费和溢出；链
表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。


缺点是：空间(指针域) 和 时间（遍历）额外耗费较大

本项目仿照书本，实现了双向链表类，在项目的实践过程中，本人理解了C++链表的基本内容以及迭代器与函数实现的方法。





\end{document}
